/* 623. 在二叉树中增加一行 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @param {number} depth
 * @return {TreeNode}
 */
// 深度优先搜索
var addOneRow = function (root, val, depth) {
	if (!root) return null
	/* depth为1时,需要创建一个新的root 并将原root作为新的root的左子节点  */
	if (depth === 1) {
		return new TreeNode(val, root, null)
	}
	/* 
        当depth为2时，需要在 root 下新增两个节点left和right 作为root
        的新子节点，并把原左子节点作为left的左子节点，把原右子节点作为right
        的右子节点 当depth 大于2时，需要递归继续往下层搜索，并将depth减1，直到
        搜索到depth 为2
    */
	if (depth === 2) {
		root.left = new TreeNode(val, root.left, null)
		root.right = new TreeNode(val, null, root.right)
	} else {
		root.left = addOneRow(root.left, val, depth - 1)
		root.right = addOneRow(root.right, val, depth - 1)
	}

	return root
}

var addOneRow = function (root, val, depth) {
	if (depth === 1) {
		return new TreeNode(val, root, null)
	}
	let curLevel = [root]
	for (let i = 1; i < depth - 1; i++) {
		const tmp = []
		for (const node of curLevel) {
			if (node.left) {
				tmp.push(node.left)
			}
			if (node.right) {
				tmp.push(node.right)
			}
		}
		curLevel = tmp
	}
	for (const node of curLevel) {
		node.left = new TreeNode(val, node.left, null)
		node.right = new TreeNode(val, null, node.right)
	}
	return root
}
